from __future__ import with_statement

import sys
from kineta.error import KinetaError
from kineta.strategy import (EmptyStrategy, FieldListStrategy,
                             TableScanStrategy, IndexScanStrategy,
                             SortStrategy, HashJoinStrategy, MergeJoinStrategy)
from kineta.cmp import cmp_values, HashableVal
import kineta.utils as utils
from decimal import Decimal


def parse_table(db, table):
    if isinstance(table, (list, tuple)):
        if len(table) == 0 or len(table) > 2:
            raise KinetaError("Invalid table specification")
        name = table[0] if len(table) == 1 else table[1]
        return db.dict.get_id(table[0], True), unicode(name)
    else:
        return db.dict.get_id(table, True), unicode(table)


def parse_limit_offset(limit, offset):
    l, o = None, None
    if limit is not None:
        l = long(limit)
        if l < 0:
            raise KinetaError("limit must be >= 0")
    if offset is not None:
        o = long(offset)
        if o < 0:
            raise KinetaError("offset must be >= 0")
    return l, o


def parse_columns(db, fields):
    ret = []
    for f in fields:
        if isinstance(f, (list, tuple)):
            if len(f) != 1:
                raise KinetaError("Invalid field %s" % f)
            ret.append(None)
        else:
            ret.append(db.dict.get_id(f, True))
    return ret


def parse_order(db, order, coldict):
    orderset = set()
    return [_parse_orderind(db, ord, orderset, coldict, "order", True)
                            for ord in order]


def parse_index(db, order):
    orderset = set()
    return [_parse_orderind(db, ord, orderset, {}, "index", False)
                            for ord in order]


def _parse_orderind(db, ord, orderset, coldict, errkind, dictro):
    o = ord
    s = "a"
    if isinstance(ord, (list, tuple)):
        l = len(ord)
        if l != 1 and l != 2:
            raise KinetaError("Invalid %s field %s" % (errkind, ord))
        s = "a"
        if l == 2:
            s = ord[1].lower()
            if s not in ("a", "d", "asc", "desc"):
                raise KinetaError("Invalid sort direction %s" % s)
        o = ord[0]
        s = str(s[0])
    o = str(o)
    if o in orderset:
        raise KinetaError("Cannot %s by field '%s' twice" % (errkind, o))
    orderset.add(o)
    col = coldict.get(o, None)
    if o not in coldict:
        col = db.dict.get_id(o, dictro)
    return (col, s)


def parse_where(db, where):
    if where is None:
        return None
    return Where(db, where)


class Where(dict):

    def __init__(self, db, where):
        for col, expr in where.iteritems():
            id = db.dict.get_id(col, True)
            if id is None:
                id = str(col)
            self[id] = self._parse_expr(expr)

    def _parse_expr(self, e):
        if not isinstance(e, (list, tuple)):
            e = [e]
        if len(e) == 0:
            raise KinetaError("Invalid empty where condition")
        if len(e) == 1:
            e = ['==', e[0]]
        op = e[0]
        if op not in _exprs:
            raise KinetaError("Unknown operator '%s'" % op)
        return _exprs[op](e)

    def test_row(self, row, results):
        ret = True
        for field in self:
            fieldval = row.get(field, None)
            res = self[field].test(fieldval)
            results[field] = res
            if not res:
                ret = False
        return ret


class Expr(object):

    def test(self, fieldval): #pragma: no cover
        raise TypeError("implement in subclass")

    def has_single_value(self):
        return False

    def get_ranges(self): #pragma: no cover
        raise TypeError("implement in subclass")

    def can_index(self):
        return True


class CmpExpr(Expr):

    def __init__(self, expr):
        needslen = self.needslen()
        exprlen = len(expr)
        if needslen is not None and exprlen != (needslen + 1):
            raise KinetaError("%s operator takes %s argument%s" %
                (expr[0], needslen, (needslen != 1) and 's' or ''))
        self.op = expr[0]
        if exprlen == 2:
            self.value = _where_value(expr[1])
        else:
            self.value = [_where_value(x) for x in expr[1:]]

    def needslen(self):
        return 1

    def test(self, fieldval):
        return self._op_impl(cmp_values(fieldval, self.value))

    def _op_impl(self, r): #pragma: no cover
        raise TypeError("implement in subclass")


class BetweenExpr(CmpExpr):

    def __init__(self, expr):
        super(BetweenExpr, self).__init__(expr)
        self.value.sort(cmp_values)

    def needslen(self):
        return 2

    def test(self, fieldval):
        return (cmp_values(fieldval, self.value[0]) >= 0 and
                cmp_values(fieldval, self.value[1]) <= 0)

    def get_ranges(self):
        return {'start_inclusive': True, 'end_inclusive': True,
                'ranges': [
                    {'begin': self.value[0], 'end': self.value[1]}]}


class ExclBetweenExpr(CmpExpr):

    def __init__(self, expr):
        super(ExclBetweenExpr, self).__init__(expr)
        self.value.sort(cmp_values)

    def needslen(self):
        return 2

    def test(self, fieldval):
        return (cmp_values(fieldval, self.value[0]) > 0 and
                cmp_values(fieldval, self.value[1]) < 0)

    def get_ranges(self):
        return {'start_inclusive': False, 'end_inclusive': False,
                'ranges': [
                    {'begin': self.value[0], 'end': self.value[1]}]}


class OutsideExpr(CmpExpr):

    def __init__(self, expr):
        super(OutsideExpr, self).__init__(expr)
        self.value.sort(cmp_values)

    def needslen(self):
        return 2

    def test(self, fieldval):
        return (cmp_values(fieldval, self.value[0]) <= 0 or
                cmp_values(fieldval, self.value[1]) >= 0)

    def get_ranges(self):
        return {'start_inclusive': True, 'end_inclusive': True,
                'ranges': [
                    {'end': self.value[0]},
                    {'begin': self.value[1]}]}


class ExclOutsideExpr(CmpExpr):

    def __init__(self, expr):
        super(ExclOutsideExpr, self).__init__(expr)
        self.value.sort(cmp_values)

    def needslen(self):
        return 2

    def test(self, fieldval):
        return (cmp_values(fieldval, self.value[0]) < 0 or
                cmp_values(fieldval, self.value[1]) > 0)

    def get_ranges(self):
        return {'start_inclusive': False, 'end_inclusive': False,
                'ranges': [
                    {'end': self.value[0]},
                    {'begin': self.value[1]}]}


class InExpr(CmpExpr):

    def __init__(self, expr):
        super(InExpr, self).__init__(expr)
        if isinstance(self.value, (tuple, list)):
            self.valueset = set(HashableVal(v) for v in self.value)
        else:
            self.valueset = set()
            self.valueset.add(HashableVal(self.value))
        self.value = [v.val for v in self.valueset]
        self.value.sort()

    def needslen(self):
        return None

    def test(self, fieldval):
        return (HashableVal(fieldval) in self.valueset)

    def get_ranges(self):
        return {'start_inclusive': True, 'end_inclusive': True,
                'ranges': [
                    {'begin': v, 'end': v} for v in self.value]}


class NotInExpr(CmpExpr):

    def __init__(self, expr):
        super(NotInExpr, self).__init__(expr)
        if isinstance(self.value, (tuple, list)):
            self.valueset = set(HashableVal(v) for v in self.value)
        else:
            self.valueset = set()
            self.valueset.add(HashableVal(self.value))
        self.value = [v.val for v in self.valueset]
        self.value.sort()

    def needslen(self):
        return None

    def test(self, fieldval):
        return (HashableVal(fieldval) not in self.valueset)

    def get_ranges(self):
        r = []
        vl = len(self.value)
        if vl > 0:
            r.append({'end': self.value[0]})
            for i in xrange(1, vl - 1):
                r.append({'begin': self.value[i - 1], 'end': self.value[i]})
            r.append({'begin': self.value[-1]})
        return {'start_inclusive': False, 'end_inclusive': False, 'ranges': r}


class EqExpr(CmpExpr):

    def has_single_value(self):
        return True

    def _op_impl(self, r):
        return (r == 0)


class NeExpr(CmpExpr):

    def _op_impl(self, r):
        return (r != 0)

    def get_ranges(self):
        return {'start_inclusive': False, 'end_inclusive': False,
                'ranges': [
                    {'end': self.value},
                    {'begin': self.value}]}


class LtExpr(CmpExpr):

    def __init__(self, expr):
        super(LtExpr, self).__init__(expr)

    def _op_impl(self, r):
        return (r < 0)

    def get_ranges(self):
        return {'start_inclusive': False, 'end_inclusive': False,
                'ranges': [
                    {'end': self.value},
                 ]}


class GtExpr(CmpExpr):

    def _op_impl(self, r):
        return (r > 0)

    def get_ranges(self):
        return {'start_inclusive': False, 'end_inclusive': False,
                'ranges': [
                    {'begin': self.value},
                 ]}


class LtEqExpr(CmpExpr):

    def __init__(self, expr):
        super(LtEqExpr, self).__init__(expr)

    def _op_impl(self, r):
        return (r <= 0)

    def get_ranges(self):
        return {'start_inclusive': True, 'end_inclusive': True,
                'ranges': [
                    {'end': self.value},
                 ]}


class GtEqExpr(CmpExpr):

    def _op_impl(self, r):
        return (r >= 0)

    def get_ranges(self):
        return {'start_inclusive': True, 'end_inclusive': True,
                'ranges': [
                    {'begin': self.value},
                 ]}


class StartsWithExpr(CmpExpr):

    def __init__(self, expr):
        super(StartsWithExpr, self).__init__(expr)
        if self.value is None:
            self.value = ""
        else:
            self.value = unicode(self.value)
        if len(self.value) > 0:
            # this *should* work as long as python sorts strings by comparing
            # code points instead of using the UCA
            if ord(self.value[-1]) >= sys.maxunicode:
                self.endvalue = None
            else:
                self.endvalue = self.value[:-1] + unichr(ord(self.value[-1])+1)

    def needslen(self):
        return 1

    def test(self, fieldval):
        return (len(self.value) > 0 and
                isinstance(fieldval, (str, unicode)) and
                fieldval.startswith(self.value))

    def get_ranges(self):
        if len(self.value) == 0:
            ranges = []
        elif self.endvalue is None:
            ranges = [{'begin': self.value}]
        else:
            ranges = [{'begin': self.value, 'end': self.endvalue}]
        return {'start_inclusive': True, 'end_inclusive': False,
                'ranges': ranges}


class ContainsExpr(CmpExpr):

    def __init__(self, expr):
        super(ContainsExpr, self).__init__(expr)
        if self.value is None:
            self.value = ""
        else:
            self.value = unicode(self.value)

    def needslen(self):
        return 1

    def test(self, fieldval):
        return (len(self.value) > 0 and
                isinstance(fieldval, (str, unicode)) and
                fieldval.find(self.value) != -1)

    def can_index(self):
        return False


class EndsWithExpr(CmpExpr):

    def __init__(self, expr):
        super(EndsWithExpr, self).__init__(expr)
        if self.value is None:
            self.value = ""
        else:
            self.value = unicode(self.value)

    def needslen(self):
        return 1

    def test(self, fieldval):
        return (len(self.value) > 0 and
                isinstance(fieldval, (str, unicode)) and
                fieldval.endswith(self.value))

    def can_index(self):
        return False


_exprs = {"between": BetweenExpr,
          "exclbetween": ExclBetweenExpr,
          "in": InExpr,
          "notin": NotInExpr,
          "outside": OutsideExpr,
          "excloutside": ExclOutsideExpr,
          "==": EqExpr,
          "!=": NeExpr,
          "<": LtExpr,
          ">": GtExpr,
          "<=": LtEqExpr,
          ">=": GtEqExpr,
          "startswith": StartsWithExpr,
          "contains": ContainsExpr,
          "endswith": EndsWithExpr}


def _get_value(x):
    if x is not None and \
        not isinstance(x, (bool, int, long, float, str, unicode, Decimal)):
        return str(x)
    if isinstance(x, Decimal):
        return float(x)
    return x


def insert_value(value, identity):
    if isinstance(value, dict):
        return identity
    if isinstance(value, (tuple, list)):
        return map(_get_value, value)
    return _get_value(value)


def update_value(value):
    return _where_value(value)


def _where_value(value):
    if isinstance(value, (tuple, list)):
        return map(_get_value, value)
    return _get_value(value)


class FieldMap(object):

    def __init__(self, table, fields, cols):
        self._map = []
        for field, col in zip(fields, cols):
            if isinstance(field, (list, tuple)):
                self._map.append(field[0])
            else:
                self._map.append((table, field, col))

    def interpolate(self, joinname, other):
        for i in xrange(len(self._map)-1, -1, -1):
            if self._map[i] == joinname:
                self._map[i:i+1] = other._map

    @property
    def field_names(self):
        return [[entry[0], entry[1]] for entry in self._map
                    if isinstance(entry, tuple)]

    def get_select_value(self, row):
        return [row.get_value(entry[0], entry[2]) for entry in self._map
                    if isinstance(entry, tuple)]


def parse_queryoptions(db, table, fields, where, joins, order, dblimits,
                       forceempty):
    islist = isinstance(joins, (tuple, list))
    if joins is None or (islist and len(joins) == 0):
        return _parse_scanoptions(db, table, fields, where, order, dblimits,
                                  forceempty, None)
    else:
        if not islist:
            joins = [joins]
        ret = JoinOptions(db, dblimits, fields)
        for join in joins:
            ret.parse_join(**utils.strkeys(join))
        fieldmap = ret.parse_scanoptions(db, table, fields, where, order,
                                         dblimits, forceempty, None)
        return ret, fieldmap


def _parse_scanoptions(db, table, fields, where, order, dblimits, forceempty,
                       joincols):
    if fields is None:
        raise KinetaError("Fields cannot be None/null")
    if not isinstance(fields, (list, tuple)):
        fields = [fields]

    cols = parse_columns(db, fields)

    ordercols = None
    if order is not None:
        if not isinstance(order, (list, tuple)):
            order = [order]
        if len(order) > 0:
            coldict = dict(zip(map(str, fields), cols))
            ordercols = parse_order(db, order, coldict)

    whereobj = parse_where(db, where)

    colset = set(cols)
    if ordercols is not None:
        colset |= set(col for col, idx in ordercols)
    if whereobj is not None:
        colset |= set(whereobj.iterkeys())
    if joincols is not None:
        colset |= set(joincols)
    if None in colset:
        colset.discard(None)

    tableid, table = parse_table(db, table)
    if forceempty:
        tableid = None

    scanopts = ScanOptions(db, tableid, table, colset, whereobj, ordercols,
                           "select", dblimits)

    return scanopts, FieldMap(table, fields, cols)


def _parse_join_on(db, on):
    if on is None:
        raise KinetaError("Join on cannot be None/null")
    r = []
    if isinstance(on, dict):
        for k, v in on.iteritems():
            id = db.dict.get_id(k, True)
            if id is None:
                id = str(k)
            r.append((id, db.dict.get_id(v, True)))
    else:
        if not isinstance(on, (tuple, list)):
            on = [on]
        for o in on:
            k = id = db.dict.get_id(o, True)
            if k is None:
                k = str(o)
            r.append((k, id))
    return r


class JoinOptions(object):

    def __init__(self, db, dblimits, fields):
        self._db = db
        self._dblimits = dblimits
        self.children = {}
        self._childorder = []
        self._joinopts = {}
        self._childmaps = {}
        self._fields = fields
        self.parent = None
        self._fieldmap = None
        self._joinfieldset = set()
        self.ordercols = []

    def parse_scanoptions(self, db, table, fields, where, order, dblimits,
                          forceempty, joinfields):
        if joinfields is not None:
            self._joinfieldset |= set(joinfields)
        (self.parent, self._fieldmap) = _parse_scanoptions(db, table, fields,
                                                          where, order,
                                                          dblimits, forceempty,
                                                          self._joinfieldset)

        for joinname, fieldmap in self._childmaps.iteritems():
            self._fieldmap.interpolate(joinname, fieldmap)

        return self._fieldmap

    def parse_join(self, table, on, fields=None, where=None, joins=None,
                   outer=False, order=None):

        if fields is None:
            fields = []

        joinon = _parse_join_on(self._db, on)

        self._joinfieldset |= set(k for k, v in joinon)
        joinvals = [v for k, v in joinon]

        islist = isinstance(joins, (tuple, list))
        if joins is None or (islist and len(joins) == 0):
            child, fieldmap = _parse_scanoptions(self._db, table, fields,
                                                    where, order,
                                                    self._dblimits, False,
                                                    joinvals)
            joinname = child.joinname
        else:
            if not isinstance(joins, (tuple, list)):
                joins = [joins]
            child = JoinOptions(self._db, self._dblimits, fields)
            for join in joins:
                child.parse_join(**utils.strkeys(join))

            fieldmap = child.parse_scanoptions(self._db, table, fields, where,
                                               order, self._dblimits, False,
                                               joinvals)
            joinname = child.parent.joinname

        self.children[joinname] = child
        self._childorder.append(joinname)
        self._joinopts[joinname] = {'on': joinon,
                                    'outer': outer}
        self._childmaps[joinname] = fieldmap

    def get_strategy(self, txn, lock):
        return self._get_strategy_internal(txn, lock, True)

    def _get_strategy_internal(self, txn, lock, toplevel):
        parentstrategy = None
        for join in self._childorder:
            joinopts = self._joinopts[join]
            joinon = joinopts['on']
            if parentstrategy is None:
                parentstrategy = self.get_sub_strategy(self.parent, txn, lock,
                                                     (pf for pf, cf in joinon))
            childstrategy = self.get_sub_strategy(self.children[join], txn,
                                                  lock,
                                                  (cf for pf, cf in joinon))
            if self._can_merge(parentstrategy, childstrategy, joinon):
                parentstrategy = MergeJoinStrategy(txn, lock, self.parent,
                                                   parentstrategy,
                                                   childstrategy, join,
                                                   joinopts)
            else:
                parentstrategy = HashJoinStrategy(txn, lock, self.parent,
                                                  parentstrategy,
                                                  childstrategy, join,
                                                  joinopts)
        if len(self.ordercols) > 0 and toplevel:
            self.parent.ordercols = self.ordercols
            parentstrategy = SortStrategy(self.parent, False, parentstrategy)

        parentstrategy.check_dup_join(set())

        return parentstrategy

    def _can_merge(self, parent, child, joinon):
        if not hasattr(parent, 'ordercols') or not hasattr(child, 'ordercols'):
            return False
        if parent.ordercols is None or child.ordercols is None:
            return False
        for flds, parentord, childord in zip(joinon, parent.ordercols,
                                             child.ordercols):
            if flds is None: # out of fields, this is ok
                break
            pf, cf = flds
            if parentord is None or childord is None \
               or parentord[-1] != childord[-1] \
               or pf != parentord[-2] \
               or cf != childord[-2]:
                return False
        return True

    def get_sub_strategy(self, opts, txn, lock, joinflds):
        if isinstance(opts, ScanOptions):
            oldorder = opts.ordercols
            opts.ordercols = [(fld, 'a') for fld in joinflds]
            s = opts.get_strategy(txn, lock)
            opts.ordercols = oldorder
            self.move_order_cols(opts)
            if not isinstance(s, SortStrategy):
                return s
            else:
                return opts.get_strategy(txn, lock)
        else:
            ret = opts._get_strategy_internal(txn, lock, False)
            self.move_order_cols(opts)
            return ret

    def move_order_cols(self, opts):
        if opts.ordercols is None or len(opts.ordercols) == 0:
            return
        for col in opts.ordercols:
            if len(col) == 2:
                self.ordercols.append((opts.joinname, col[0], col[1]))
            else:
                self.ordercols.append(col)
        opts.ordercols = None


def get_field_list_strategy(db, txn, lock, tableid):
    return FieldListStrategy(db, txn, lock, tableid)


class ScanOptions(object):

    def __init__(self, db, tableid, joinname, colset, whereobj, ordercols, op,
                 dblimits):
        self.db = db
        self.tableid = tableid
        self.joinname = joinname
        self.colset = colset
        self.whereobj = whereobj
        self.ordercols = ordercols
        self.op = op
        self.dblimits = dblimits

    def get_strategy(self, txn, lock):
        indexes = None
        if self.tableid is not None:
            indexes = self.db.tables.index_list(lock, self.tableid)

        if self.tableid is None or indexes is None:
            return EmptyStrategy(self)
        if self.whereobj is None and self.ordercols is None:
            # really simple, just scan the table and return
            # all the rows unordered
            return TableScanStrategy(txn, lock, self)
        if self.whereobj is None or self.ordercols is None:
            # we have either constraints or ordering but not both
            if self.whereobj is None:
                idx = _find_order_index(indexes, self.colset, self.ordercols)
                if idx is None:
                    return SortStrategy(self, True,
                                        TableScanStrategy(txn, lock, self))
            else: # ordercols is None
                idx = _find_where_index(indexes, self.colset, self.whereobj)
                if idx is None:
                    return TableScanStrategy(txn, lock, self)
            # if we found an index then either way our strategy is the same
            return IndexScanStrategy(txn, lock, idx, self)

        # both constraints and ordering are present
        oidx = _find_order_index(indexes, self.colset, self.ordercols)
        widx = _find_where_index(indexes, self.colset, self.whereobj)

        if oidx is None and widx is None: # no useful indexes apparantly
            return SortStrategy(self, True, TableScanStrategy(txn, lock, self))

        (idx, needssort) = _choose_index(oidx, widx, indexes)

        if needssort:
            return SortStrategy(self, True,
                                IndexScanStrategy(txn, lock, idx, self))
        else:
            return IndexScanStrategy(txn, lock, idx, self)


def _find_order_index(indexes, colset, ordercols):
    hasalloutputcols = set()
    matches = []
    ordercolsnoempty = filter(lambda x: x[0] is not None, ordercols)
    colsnostr = utils.no_strings(colset)
    for idx in indexes:
        num = 0
        reverse = False
        for idxordercol, ordercol in zip(idx, ordercolsnoempty):
            num += 1
            col, dir = ordercol
            idxcol, idxdir = idxordercol
            # index isnt sorting by this column, forget it
            if col != idxcol:
                break
            # if the first column is the wrong direction all the others
            # must be as well
            if num == 1:
                reverse = dir != idxdir
            elif dir != idxdir and not reverse:
                break
            # end of the order columns, we're good
            if num == len(ordercolsnoempty):
                matches.append(idx)
                if len(colsnostr - set(ic for ic, id in idx)) == 0:
                    hasalloutputcols.add(idx)
                break
    if len(matches) == 0:
        return None
    if len(matches) == 1:
        return matches[0]

    def compare_indexes(x, y):
        # compare output columns
        xin = 1 if x in hasalloutputcols else 0
        yin = 1 if y in hasalloutputcols else 0
        r = cmp(xin, yin)
        if r != 0:
            return r
        # compare timestamps
        return cmp(indexes[x].timestamp, indexes[y].timestamp)
    matches.sort(compare_indexes)
    return matches[-1]


def _find_where_index(indexes, colset, whereobj):
    hasalloutputcols = set()
    cmpcolcounts = {}
    matches = []
    colsnostr = utils.no_strings(colset)
    for idx in indexes:
        cmpcount = 0
        for col, dir in idx:
            if col in whereobj:
                if whereobj[col].can_index() and \
                   (cmpcount == 0 or whereobj[col].has_single_value()):
                    cmpcount += 1
                else:
                    break
            else:
                break
        if cmpcount > 0:
            matches.append(idx)
            if len(colsnostr - set(ic for ic, id in idx)) == 0:
                hasalloutputcols.add(idx)
            cmpcolcounts[idx] = cmpcount

    if len(matches) == 0:
        return None
    if len(matches) == 1:
        return matches[0]

    def compare_indexes(x, y):
        # compare output columns
        xin = 1 if x in hasalloutputcols else 0
        yin = 1 if y in hasalloutputcols else 0
        r = cmp(xin, yin)
        if r != 0:
            return r
        # compare comparison fields
        r = cmp(cmpcolcounts[x], cmpcolcounts[y])
        if r != 0:
            return r
        # compare timestamps
        return cmp(indexes[x].timestamp, indexes[y].timestamp)
    matches.sort(compare_indexes)
    return matches[-1]


def _choose_index(oidx, widx, indexes):
    if oidx is None:
        return (widx, True)
    if widx is None or oidx == widx:
        return (oidx, False)
    # unfortunately we need statistics to make an informed decision here.
    # the problem is that for a really huge dataset that needs to be in a
    # particular order, the ordered index will probably be the better one
    # because the cost of doing a sort is so large.

    # we'll just take a shortcut and use the most recent index.  The sort
    # strategy can choose to create a new index or set the timestamp on an
    # existing index later if neccessary
    r = cmp(indexes[oidx].timestamp, indexes[widx].timestamp)
    if r < 0:
        return (widx, True)
    else:
        return (oidx, False)
